CF487B Strip

一道并不难的 dpdp 题。转移式很好列:

dp[i]=min{dp[j]+1}    (0jil &&max(j+1,i)min(j+1,i)<=s)dp[i]=min\{ dp[j]+1 \} ~~~~ (0 \le j \le i - l~\&\&max(j+1,i)-min(j+1,i)<=s)

看到区间的最大值与最小值之差,我们很容易想到用 stst 表维护。这样可以Θ(n2)\Theta(n^2)解决。

很显然的一个结论是,决策点是单调递增的。因为 ii 不断向右,区间的最值递增,决策点也必须向右调整。

并且,为了使答案更优,我们每次一定会选择最靠左的那个决策点。

所以,只需要维护最左边的决策点即可,转移复杂度Θ(n)\Theta(n)

总时间复杂度Θ(nlogn+n)\Theta(nlogn+n)

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define INF 0x3f3f3f3f

const int MAXN = 100000 , MAXK = 20;
int n , l , s , a[ MAXN + 5 ] , f[ 2 ][ MAXN + 5 ][ MAXK + 5 ]; //0->max 1->min
int dp[ MAXN + 5 ];

void Init( ) {
    memset( f[ 1 ] , 0x3f , sizeof( f[ 1 ] ) );
    
    for( int i = 1 ; i <= n ; i ++ )
        f[ 0 ][ i ][ 0 ] = f[ 1 ][ i ][ 0 ] = a[ i ];
    for( int j = 1 ; ( 1 << j ) <= n ; j ++ )
        for( int i = 1 ; i + ( 1 << j ) - 1 <= n ; i ++ ) {
            f[ 0 ][ i ][ j ] = max( f[ 0 ][ i ][ j - 1 ] , f[ 0 ][ i + ( 1 << j - 1 ) ][ j - 1 ] );
            f[ 1 ][ i ][ j ] = min( f[ 1 ][ i ][ j - 1 ] , f[ 1 ][ i + ( 1 << j - 1 ) ][ j - 1 ] );
        }
}
int Query( int l , int r ) {
    int k = log2( r - l + 1 );
    return max( f[ 0 ][ l ][ k ] , f[ 0 ][ r - ( 1 << k ) + 1 ][ k ] ) - min( f[ 1 ][ l ][ k ] , f[ 1 ][ r - ( 1 << k ) + 1 ][ k ] );
}

int main( ) {
    scanf("%d %d %d",&n,&s,&l);
    for( int i = 1 ; i <= n ; i ++ ) 
        scanf("%d",&a[ i ]);
    Init( );

    memset( dp , 0x3f , sizeof( dp ) ); dp[ 0 ] = 0;
    int chk = 0;
    for( int i = l ; i <= n ; i ++ ) {
        while( ( i - chk >= l && ( Query( chk + 1 , i ) > s ) || dp[ chk ] == INF ) ) chk ++;
        if( i - chk >= l ) dp[ i ] = dp[ chk ] + 1;
    }
    printf("%d", dp[ n ] == INF ? -1 : dp[ n ] );
    return 0;
}